The invention relates generally to the art of computer graphics and more particularly to the modeling and moving of large systems of geometry such as hair and fur which must extend naturally from an arbitrary surface. Such large systems in the natural world share properties with the shape of the underlying surfaces as well as the shape defined by the systems themselves. This invention relates to computer methods that can render and model deformable systems of geometry that have stable dynamics when viewing the object that has been rendered.
Modeling and moving extremely large systems of geometry in a stable surfaced based volume has been a central problem in computer graphics and computer animation systems. Hair, in particular, has long presented computer artists with intractable problems when trying to define, shape, and manipulate the millions of geometrical elements which comprise a usual occurrence of hair.
Problems arising from previous methods involve memory management of such large systems of geometry, efficient definition distortion required on a straight line required to create the geometry (like hair), and how to maintain proper orientation of the details of the geometry as it flexes and moves.
Coordinate systems in general are defined by three vectors which represent the pseudo x,y, and z axis respectively and scalars thereof. Most systems of derived matrices comprise only two vectors and an arbitrary xe2x80x9cupxe2x80x9d vector which is made perpendicular to the first two vectors by a cross product of the first two vectors. When placed in a matrix, the matrix defines a local coordinate system which may also be inverted. This means, that you can multiply a point in Cartesian space by a local matrix to perform local distortions of orientation and scale, and then return the point to Cartesian space by applying the inverse of the matrix to the point. A typical use of a local matrix is a rotation matrix, which is constructed from euler angles for the three axis, then applied to a set of points to orient an object to a local coordinate system. Another common use of a matrix is a perspective matrix. A perspective matrix contains the necessary distortion of Cartesian space to it""s projection on a flat viewing plane, usually scaling points close to the plane larger, and ones further away smaller.
Hoppe, Hugues, xe2x80x9cProgressive Meshes,xe2x80x9d Computer Graphics (SIGGRAPH) 96 Conference Proceedings), pp. 99-108 (1996).
Eck, Matthias, and Hugues Hoppe, xe2x80x9cAutomated Reconstruction of B-Spline Surfaces of Arbitrary Topological Type,xe2x80x9d Computer Graphics (SIGGRAPH 96 Conference Proceedings), pp. 325-334 (1996).
Halstead, Mark, et al. xe2x80x9cEfficient, Fair Interpolation Using Catmull-Clark Surfaces,xe2x80x9d Computer Graphics (SIGGRAPH 93 Conference Proceedings), pp. 35-44 (1993).
Krishnamurthy, Venkat and Marc Levoy, xe2x80x9cFitting Smooth Surfaces to Dense Polygon
Meshes,xe2x80x9d Computer Graphics (SIGGRAPH 96 Conference Proceedings), pp. 313-324 (1996).
Hoppe, Hugues, et al. xe2x80x9cPiecewise Smooth Surface Reconstruction,xe2x80x9d Computer Graphics (SIGGRAPH 94 Conference Proceedings), pp. 295-302 (1994).
Doo, D. and M. Savin, xe2x80x9cBehavior of Recursive Division Surfaces Near Extraordinary Points,xe2x80x9d Computer Aided Design, 10:356-360 (1978).
Catmull, E., and Clark, J., xe2x80x9cRecursively Generated B-Spline Surfaces on Arbitrary Topological Meshes,xe2x80x9d Computer Aided Design, 10:350-355 (1978).
Lee, Yuencheng, et al., xe2x80x9cRealistic Modeling for Facial Animation,xe2x80x9d Computer Graphics (SIGGRAPH 95 Conference Proceedings), pp. 55-62 (1995).
Certain, Andrew, et al., xe2x80x9cInteractive Multiresolution Surface Viewing,xe2x80x9d Computer Graphics (SIGGRAPH 96 Conference Proceedings), pp. 91-98 (1996).
Nasri, A. H., xe2x80x9cBoundary-Corner Control in Recursive-Subdivision Surfaces,xe2x80x9d Computer Aided Design, vol. 2, pp. 405-410 (1990).
Nasri, Ahmad H., xe2x80x9cSurface Interpolation of Irregular Networks with Normal Conditions,xe2x80x9d Computer Aided Geometric Design, 8:89-96 (1991).
Nasri, Ahman H., xe2x80x9cPolyhedral Subdivision Methods for Free-Form Surfaces,xe2x80x9d ACM Transactions on Graphics, 6:29-73 (1987).
Ball, A. A. and D. J. T. Storry, xe2x80x9cA Matrix Approach to the Analysis of Recursively Generated B-Spline Surfaces, xe2x80x9d Computer-Aided Design, 18:437-442 (1986).
Ball, A. A. and D. J. T. Storry, xe2x80x9cAn Investigation of Curvature Variations Over Recursively Generated B-Spline Surfaces,xe2x80x9d ACM Transactions on Graphics, 9:424-437 (1990).
Ball, A. A. and D. J. T. Storry, xe2x80x9cConditions for Tangent Plane Continuity Over Recursively Generated B-Spline Surfaces,xe2x80x9d ACM Transactions on Graphics, 7:83-102 (1988).
Reif, U., A Unified Approach to Subdivision Algorithms, Department of Mathematics, University of Stuttgart.
Warren, Joe, Subdivision Methods for Geometric Design (1994).
Dyn, Nira and David Levin, xe2x80x9cAnalysis of Asymptotically Equivalent Binary Subdivision Schemes,xe2x80x9d School of Mathematical Sciences, Tel-Aviv University.
Derfel, G., N. Dyn, and D. Levin, xe2x80x9cGeneralized Refinement Equations and Subdivision Processes,xe2x80x9d Ben-Gurion University and Tel-Aviv University.
Dyn, N., S. Hed, and D. Levin, Subdivision Schemes for Surface Interpolation, Department of Mathematics, Tel Aviv University (1993).
Dyn, N. and D. Levin, xe2x80x9cInterpolating Subdivision Schemes for the Generation of Curves and Surfaces,xe2x80x9d Multivariate Interpolation and Approximation, W. Haussmann and K.
Jetter, eds. Birkhauser, Verlag, Basel, pp. 91-106 (1990).
Bajaj, Chandrajit L. et al., xe2x80x9cAdaptive Reconstruction of Surfaces and Scalar Fields from Dense Scattered Trivariate Data,xe2x80x9d Computer Science Technical Report, pp. 1-19 (1995).
Gudukbay, U. et al., xe2x80x9cA Spring Force Formulation For Elastically Deformable Models,xe2x80x9d Computer and Graphics, 21:3:335-346 (May-June 1991) XP004083258.
Gudukbay, U. and Bulent Ozguc, xe2x80x9cAnimation of Deformable Models,xe2x80x9d Computer-Aided Design, 26:12:868-875 (Dec. 1, 1994) XP000500985.
Hahn, James K., xe2x80x9cRealistic Animation of Rigid Bodies,xe2x80x9d Computer Graphics (Siggraph ""88 Conference Proceedings) 22:4:299-308 (Aug. 1-5, 1988) XP002084382.
Hoppe, Hugues, xe2x80x9cView-Dependent Refinement of Progressive Meshes,xe2x80x9d Computer Graphics (SIGGRAPH 97 Conference Proceedings) pp. 189-198 (Aug. 3-8, 1997) XP002085290.
Sarraga et al., xe2x80x9cFree-Form Surfaces in GMSolid: Goals and Issues,xe2x80x9d Solid Modeling by Computers From Theory to Applications, M. S. Pickett and J. W. Boyse, editors, Plenum Press, 1984, pp. 187-209.
Sederberg et al., xe2x80x9cFree-Form Deformation of Solid Geometric Models,xe2x80x9d SIGGRAPH ""86, ACM, vol. 20, No. 4, 1986, pp. 151-160.
The U.S. Pat. No. 6,037,949 and the U.S. Pat. No. 5,796,400 which are part of the prior art show use of texture mapping and other uses of scaler fields on subdivision surfaces. The methods, while different in the respect that they don""t directly relate to dynamic computer generated hair, are relevant in the use of scalar fields and parameters which will be interpolated over a 2 dimensional surface in a 3D world space. Therefore they can be very instructive as to what is considered as skill in the art in terms of defining and computing the value of scaler fields over a set of points on a surface to model or animate. These patents mention and describe these techniques in computer graphics and computer animation as well as appropriate algorithms used by animators by people skilled in the art on a regular basis.
Since this patent application improves on these patents by a method that uses mesh and coordinates, it is similar to the prior art, but different in many respects based on using coordinates that have underconnectivity and using guide columns having the vector coordinates located thereon and deforming the columns and rendering as will be apparent from the description in this application.
The present invention, by providing a method for defining stable and arbitrary coordinate systems comprised of a system of matrices that shares similarity with an underlying surface, allows for the pragmatic creation of temporary geometry which may be created on demand, deleted from memory, and repeated on demand with very few actual parameters, thus minimizing memory requirements for recalling such a large system of geometry in a piece-wise fashion.
Under such method, only a straight, undeformed version of a single instance of the geometry (a single hair for example), and the coordinate system described above, must be stored to create and render an infinite set of occurrences across the coordinate system, which provides shape in a volumetric way.
Previous methods use the decades old method of bump mapping, or xe2x80x98Blinn Shadingxe2x80x99. Blinn Shading is a method for creating the appearence of bumps on a surface as a shading artifact by xe2x80x98wobblingxe2x80x99 the normal of a surface, which is in-tern used to shade a point on the surface. The normal is xe2x80x98wobbledxe2x80x99 by constructing a coordinate system out of the underlying surface and rotating the normal vector. This provides us with a method by which we may perform certain distortions of the surrounding space by providing an anchor by which we may rotate and scale local to the root of a surrounding volume. For instance, if you were to grow a hair from a surface, you could then rotate it about it""s root using the above method. This method solves for coordinate system of transformation at the root of the hair, but does not provide for the rest of the hair as the volume it creates only has similarity with the surface, and does not share any properties with the hair itself.
Another great difficulty in computer graphics simulation of large systems like hair, has been how to move the geometry using physical simulation. This type of arbitrary volume allows us to run conventional physical simulation on chains formed by the columns of this arbitrary lattice structure, thus distorting the very space that the large system of geometry is passed through allowing for a low resolution definition of this very detailed system.
A common way of representing a spatial distortion for a volume is an FFD (free form deformation lattice). FFD""s have the limitation of a grid structure in their definition, and are not suitable for this type of deformation since the underlying surface which drives the deformation may not be connected in a grid-like fashion, such as in the case of a polygonal mesh. FFD""s have been employed for distorting space extending from a spline patch primative, since patches have a grid like parameterisation, but this method will fail where one patch edge meets another, because there is no continuity across patch edges, FFD methods are extremely difficult to manage. With a coordinate system such as the one here described, by joining primitives at the base of the deformation space in an arbitrary way, we may have surface continuity, thus spatial continuity as this connectivity gets propagated up the lattice.
By using the underlying connectivity of the surface that this lattice is derived from at each segment of each column, the coordinate system gains the property of stable orientation at each level of the lattice structure. This connectivity simply points at the column""s neighbor for what is known as an xe2x80x98up vectorxe2x80x99 for an orienting matrix. In the case of hair, this system would share properties of both the underlying surface, as well as the hairs which are grown from said surface. The combination of these two gives us a coordinate system which may be derived, or re-derived (in animation ) from changes in either the xe2x80x98hairxe2x80x99 or the surface.
Because this connectivity is static, severe motion and xe2x80x98tanglexe2x80x99 may be applied to the columns of this lattice structure without failure, usually caused by a common problem called xe2x80x98gimbal lockxe2x80x99 which usually occurs in simulated motion of chain-like kinematic structures. Gimbal lock problems happen because dynamic chains usually construct their orientation matrices with a static up vector, such as the xe2x80x98yxe2x80x99 axis. Creating a matrix in this fashion requires a cross product with the direction of the chain link. A static up vector like this will tend to produce a 180 degree flip in orientation when the chain faces in the same or nearly the same direction as the up-vector, which can occur frequently in a large system such as hair.
With the coordinate system described here, each link of the chain has it""s own up vector based on it""s connectivity with it""s neighbors. Because of this, the possibility of a chain facing the same direction as it""s up-vector is reduced by an enormous factor, and failures to produce a valid orientation matrix are virtually eliminated.
Another problem in computer graphics with large systems such as hair arises from not having coordinate systems which define an entire volume in this fashion and is one of xe2x80x98stylingxe2x80x99. Hair, for instance, has xe2x80x98curlxe2x80x99, and xe2x80x98kinkxe2x80x99. While these types of transformations may be easily described in Cartesian space, carrying them forward into the space of hair is impossible to do in any sort of stable manor without defining a smooth and stable volume of local coordinate systems by which we may derive orientation and anchors for such transformation at any point in the volume. This is particularly problematic when the hair is bending and twisting such as it does in a dynamic simulation, the coordinate system must contain properties of this movement to anchor and orient such transformations locally throughout the system or the curls and kinks will appear to distort as the hair bends. Describing a stable, continuous coordinate system such as we describe solves for this problem and maintains proper shape as the hair bends and twists from an animated dynamic system.
Failure of previous methods is most apparent in highly flexible dynamic systems and limits them to relatively xe2x80x98stiffxe2x80x99 animation which is limited to flexibility with only very few degrees of freedom of motion. This type of coordinate system has no such limitations with respect to motion, flexibility and realistic simulation.
Another by-product of this approach is the ability to produce actual geometry with continuous and stable orientation along it""s length, where previous approaches yield undesirable xe2x80x98twistsxe2x80x99 and xe2x80x98flipsxe2x80x99 because of their use of arbitrary up vectors for orientation.